class Solution
{
public:
    long long countPalindromePaths(vector<int> &parent, string s)
    {
        int n = parent.size();

        // 建树
        unordered_map<int, vector<int>> tree;
        for (int i = 1; i < n; ++i)
        {
            tree[parent[i]].push_back(i);
        }

        // bfs确定每个节点模式
        vector<int> nodePattern(n);
        nodePattern[0] = 0;
        queue<int> q;
        q.push(0);
        while (!q.empty())
        {
            int node = q.front();
            q.pop();
            for (int child : tree[node])
            {
                nodePattern[child] = nodePattern[node] ^ (1 << (s[child] - 'a'));
                q.push(child);
            }
        }

        // 统计节点模式, 如果两个模式相同或者有一位不同, 那么可以构成回文
        unordered_map<int, int> patternCount;
        long long result = 0;

        for (int i = 0; i < n; ++i)
        {
            int pattern = nodePattern[i];

            // 相同的模式可以构成回文
            result += patternCount[pattern];

            // 只有一位不同的模式可以构成回文
            for (int j = 0; j < 26; ++j)
            {
                int needPattern = pattern ^ (1 << j);
                if (patternCount.count(needPattern))
                {
                    result += patternCount[needPattern];
                }
            }
            ++patternCount[pattern];
        }

        return result;
    }
};